/*
 * @lc app=leetcode.cn id=22 lang=java
 *
 * [22] 括号生成
 */

// @lc code=start

import java.util.List;
import java.util.ArrayList;

class Solution {

    List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {

        dfs(n, 0, 0, "");
        return res;
        // 使用DFS
    }

    private void dfs(int n, int lc, int rc, String cur) {
        if(lc == n && rc == n) {
            res.add(cur);
        
        }else {
            if(lc < n) {
                dfs(n, lc + 1, rc, cur + "(");
            }
            if(rc < lc && rc < n) {
                dfs(n, lc, rc + 1, cur + ")");
            }
        }
    }



}
// @lc code=end

